# -*- coding:utf-8 -*-
# 
"""
题目url: https://leetcode-cn.com/problems/rotting-oranges/
描述：
    在给定的网格中，每个单元格可以有以下三个值之一：
        值 0 代表空单元格；
        值 1 代表新鲜橘子；
        值 2 代表腐烂的橘子。
    每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
    返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
"""
class Solution:
    
    def orangesRotting(self, grid):
        row = len(grid)
        col = len(grid[0])
        rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2} # 腐烂集合
        time = 0
        while rotten:
            new_rotten = set()
            for i, j in rotten:
                 # 正方向感染
                for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # 上、下、左、右
                    if i + di >= row or i + di < 0 or j + dj >= col or j + dj < 0:
                        continue
                    if grid[i + di][j + dj] == 1:
                        grid[i + di][j + dj] = 2
                        new_rotten.add((i + di, j + dj))
            rotten = new_rotten
            if rotten:
                time += 1
        if {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}:
            return -1
        return time

        
res = Solution().orangesRotting([[2,1,1],[1,1,0],[0,1,1]])
print(res)

